#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
//完成归并排序


//归并
void merge(std::vector<int> &arr, int L, int mid, int R)
{
	std::vector<int> temp(R-L+1);
	int i = 0;
	int l = L, r = mid + 1;
	while (l <= mid && r <= R)
	{
		temp[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
	}
	while (l <= mid)
	{
		temp[i++] = arr[l++];
	}
	while (r <= R)
	{
		temp[i++] = arr[r++];
	}
	memcpy(arr.data() + L, temp.data(), (R-L+1)*sizeof(int));
}
void process(std::vector<int> &arr, int L, int R)
{
	if (L == R)
	{
		return ;
	}
	int mid = L + ((R - L) >> 1);
	process(arr, L, mid);
	process(arr, mid + 1, R);
	merge(arr, L, mid, R);
}

void mergeSort(std::vector<int> &arr)
{
	process(arr, 0, arr.size() - 1); 
}
int main()
{
	std::vector<int> arr{3,4,5,3,1,7,8,7,0,13,22,4,1,2,6,7382,33,2231,312312,4341,3131,1231241,1231232,122,3213,132312,3124,5754,7765,32423,4654,234234,23342,345,757,87,980};
	std::vector<int> b;
	b.assign(arr.begin(), arr.end());
	mergeSort(arr);
//	for (auto i : arr)
//	{
//		std::cout << i << std::endl;
//	}
	std::sort(b.begin(), b.end());
	if (b != arr)
	{
		std::cout << "sort failure!!" << std::endl;
	}
	else
	{
		std::cout << "sort success!!!!" << std::endl;
	}

	return 0;
}